package com.leetcode;


import java.util.TreeSet;

/**
 * 220. 存在重复元素 III
 * 滑动窗口 + 有序集合
 *
 * @author fy
 * @date 2022/4/8 21:58
 */
public class Solution220 {

    public boolean containsNearbyAlmostDuplicate1(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            Long ceil = set.ceiling((long)nums[i] - t);
            long sum = (long)nums[i] + (long)t;
            if (ceil != null && ceil <= sum) {
                return true;
            }
            set.add((long)nums[i]);
            if (set.size() == k + 1) {
                set.remove((long)nums[i - k]);
            }
        }
        return false;
    }

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length < 2) {
            return false;
        }
        TreeSet<Long> treeSet = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            Long floor = treeSet.floor((long)nums[i] + t);
            if (floor != null && floor >= (long)nums[i] - t) {
                return true;
            }
            treeSet.add((long)nums[i]);
            if (i > k) {
                treeSet.remove((long)nums[i - k]);
            }
        }
        return false;
    }

    public static void main(String[] args) {
//        int[] nums = new int[]{1, 2, 3, 1};
//        int k = 3;
//        int t = 0;

        int[] nums = new int[]{2147483640, 2147483641};
        int k = 1;
        int t = 100;

        boolean res = new Solution220().containsNearbyAlmostDuplicate(nums, k, t);
        System.out.println(res);
    }

}
